import javax.sound.sampled.Line;
import java.lang.reflect.Field;
import java.util.LinkedList;

/**
 * @author zx
 * @date date 2019-11-29 21:54:17
 * 合并两个有序链表
 */
public class MergeLinkedList {

    private static class Node{
        int value;
        Node next,prev;
        public Node(int value) {
            this.value = value;
        }
        public Node(){
        }
    }


    public static Node merge(Node node1, Node node2){
        Node result = new Node();
        Node finalResult = result;
        while (node1 != null && node2 != null){
            if(node1.value >= node2.value){
                result.next = node2;
                node2 = node2.next;
            }else{
                result.next = node1;
                node1 = node1.next;
            }
            result = result.next;
        }
        if(node1 !=null){
            result.next = node1;
        }else if(node2 != null){
            result.next = node2;
        }

        return finalResult.next;
    }

    public static void print(Node node){
        while (node != null){
            System.out.print(node.value);
            node = node.next;
        }
    }

    public static void main(String[] args) {
        Node head1= new Node();
        Node node1 = head1;
        for (int i = 0; i < 4; i++) {
            node1.next = new Node(i);
            node1 = node1.next;
        }
        Node head2= new Node();
        Node node2 = head2;
        for (int i = 0; i < 7; i++) {
            node2.next = new Node(i+2);
            node2 = node2.next;
        }
        print(merge(head1.next, head2.next));

    }
}
